/*
 * COMP6471 Project
 *  
 * This file is created by Yuan Tao (ewan.msn@gmail.com)
 * Licensed under GNU GPL v3
 * 
 * $Author: ewan.msn@gmail.com $
 * $Date: 2011-11-05 19:50:51 +0000 (Sat, 05 Nov 2011) $
 * $Rev: 48 $
 * $HeadURL: http://comp6471.googlecode.com/svn/Project4/src/kklib/Layout.java $
 * 
 */

package kklib;

import java.util.ArrayList;

import util.logger;


public class Layout {
	// attributes of the txt file.
	public String fileFullname;
	public ArrayList<String> txtFileData = new ArrayList<String>();
	public ArrayList<String> txtFileFormulas = new ArrayList<String>();  // store the text format formulas
	
	// attributes of the layout
	public static final int MAX_GAME_SIZE = 6;
	public String gameName;
	public int gameSize = 4;
	public ArrayList<Cage> cages = new ArrayList<Cage>();
	private int numOfSolutions;			// number of possible solutions
	public static final int MAX_SOLUTIONS = 8;
	public static final int MAX_LAYOUTSOLUTIONS = 4;
	public static final int MAX_POSSIBLE_LAYOUTS = 50;
	
	// to store the cells by connecting them in rows or columns
	public ArrayList<Cell> rows = new ArrayList<Cell>();
	public ArrayList<Cell> columns = new ArrayList<Cell>();
	
	
	// get property
	public int getNumOfSolutions() {
		return numOfSolutions;
	}
	
	// list of cages got from the input file of project 2.
	public ArrayList<Cage> availableCages = new ArrayList<Cage>();
	
	// get the next cage type from cage list.
	// the cages are stored in the list from the smallest type to the biggest one.
	private int getNextTypeOfCage(int curType) {
		for (int i = curType; i < availableCages.size(); i++) {
			if (availableCages.get(i).cageNum > 0) {
				return availableCages.get(i).cageType;
			}
		}
		
		return 0;
	}
	
	// get the type of a available cage from the list
	private int getTypeOfAvailableCage() {
		for (int i = 0; i < availableCages.size(); i++) {
			if (availableCages.get(i).cageNum > 0) {
				return availableCages.get(i).cageType;
			}
		}
		
		return 0;
	}
	
	// check if the cell of the layout has been filled in
	private boolean ifCellAdded(int x, int y) {
		Cage c;
		
		for (int i = 0; i < cages.size(); i++) {
			c = cages.get(i);
			for (int j = 0; j < c.cells.size(); j++) {
				if (c.cells.get(j).x == x && c.cells.get(j).y == y) {
					return true;
				}
			}
		}
		return false;
	}

	// check if the cage can be put into the layout
	private int ifCageFitIn(int curType) {
		int x = 0, y = 0;
		boolean exitLoop = false;
		
		// find the first empty cell by rows		
		for (y = 0; y < gameSize && !exitLoop; y++) {
			for (x = 0; x < gameSize; x++) {
				if (!ifCellAdded(x, y)) {
					exitLoop = true;
					y--;
					break;
				}
			}
		}
		
		// check if such type of cage can be fit into the layout
		boolean ifTypeOK = false;
		Cage c = new Cage();
		
		switch (curType) {
		case 1:		// 1 means type A
			ifTypeOK = true;		// always OK
			break;
		case 2:
			if (x + 1 < gameSize && !ifCellAdded(x + 1, y)) {
				Cell e = new Cell();
				
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 3:
			if (y + 1 < gameSize && !ifCellAdded(x, y + 1)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 4:
			if (x + 2 < gameSize && !ifCellAdded(x + 1, y) && !ifCellAdded(x + 2, y)) {
				Cell e = new Cell();
				
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 2;
				e.y = y;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 5:
			if (y + 2 < gameSize && !ifCellAdded(x, y + 1) && !ifCellAdded(x, y + 2)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 2;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 6:
			if (x + 1 < gameSize && y + 1 < gameSize 
					&& !ifCellAdded(x, y + 1) && !ifCellAdded(x + 1, y + 1)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y + 1;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 7:
			if (x + 1 < gameSize && y + 1 < gameSize 
					&& !ifCellAdded(x, y + 1) && !ifCellAdded(x + 1, y)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 8:
			if (x + 1 < gameSize && y + 1 < gameSize 
					&& !ifCellAdded(x + 1, y) && !ifCellAdded(x + 1, y + 1)) {
				Cell e = new Cell();
				
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y + 1;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		case 9:
			if (x > 0 && y + 1 < gameSize 
					&& !ifCellAdded(x, y + 1) && !ifCellAdded(x - 1, y + 1)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x - 1;
				e.y = y + 1;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
			
		case 10:
			if (x + 4 < gameSize 
					&& !ifCellAdded(x + 1, y) && !ifCellAdded(x + 2, y)
					&& !ifCellAdded(x + 3, y) && !ifCellAdded(x + 4, y)) {
				Cell e = new Cell();
				
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 2;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 3;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 4;
				e.y = y;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
			
		case 11:
			if (x + 2 < gameSize && y + 4 < gameSize
					&& !ifCellAdded(x, y + 1) && !ifCellAdded(x, y + 2)
					&& !ifCellAdded(x, y + 3) && !ifCellAdded(x, y + 4)
					&& !ifCellAdded(x + 1, y + 4) && !ifCellAdded(x + 2, y + 4)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 2;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 3;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 4;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y + 4;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 2;
				e.y = y + 4;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
			
		case 12:
			if (x + 2 < gameSize && y + 4 < gameSize
					&& !ifCellAdded(x, y + 1) && !ifCellAdded(x, y + 2)
					&& !ifCellAdded(x, y + 3)
					&& !ifCellAdded(x + 1, y) && !ifCellAdded(x + 2, y)
					&& !ifCellAdded(x + 3, y) && !ifCellAdded(x + 4, y)
					&& !ifCellAdded(x + 1, y + 3) && !ifCellAdded(x + 2, y + 3)) {
				Cell e = new Cell();
				
				e.x = x;
				e.y = y + 1;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 2;
				c.cells.add(e);
				e = new Cell();
				e.x = x;
				e.y = y + 3;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 2;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 3;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 4;
				e.y = y;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 1;
				e.y = y + 3;
				c.cells.add(e);
				e = new Cell();
				e.x = x + 2;
				e.y = y + 3;
				c.cells.add(e);
				ifTypeOK = true;
			}
			break;
		}
		
		if (!ifTypeOK) {
			return -1;
		}

		Cell e = new Cell();
		e.x = x;
		e.y = y;
		c.cells.add(e);		// add current cell as well

		// add the cage to the layout
		c.cageType = curType;
		cages.add(c);

		// decrease one available cage from cage list
		availableCages.get(curType - 1).cageNum--;
		
		// check if layout is full of cells.
		int cnt = 0;
		
		for (int i = 0; i < cages.size(); i++) {
			cnt += cages.get(i).cells.size();
		}
		if (cnt < gameSize * gameSize) {
			return 1;		// layout is not full
		}

		return 0;			// layout is full
	}
	
	// delete the last cage added to the layout
	private int deleteLastCage() {
		int index = cages.size() - 1;
		
		if (index < 0) {
			return 0;
		}
		
		// increase the number of available cage
		int ret = cages.get(index).cageType;
		availableCages.get(ret - 1).cageNum++;	
				
		// remove the last cage		
		cages.remove(index);
		return ret;
	}
	
	// replace the last cage with next type of available cages from the list
	private int replaceLastCage() {		
		int curType = 0;
		
		do {
			curType = deleteLastCage();
			if (curType == 0) {
				// have tried all the cages including the first one
				return 0;
			}
			curType = getNextTypeOfCage(curType);
		} while (curType == 0);
		
		return curType;
	}
	
	// store the result to be printed
	private int copyResult(ArrayList<Integer> pLayout) {
		for (int i = 0; i < gameSize * gameSize; i++) {
			pLayout.add(0);
		}
		
		ArrayList<Cell> c;
		int pad = 1;
		
		for (int i = 0; i < cages.size(); i++) {
			c = cages.get(i).cells;
			for (int j = 0; j < c.size(); j++) {
				pLayout.set(c.get(j).x + c.get(j).y * gameSize, pad);
			}
			pad++;
		}
		return 0;
	}
	
	// generate all the possible layouts from the list of cages. 
	public int generatePossibleLayoutFromCages(ArrayList<ArrayList<Integer>> possibleLayouts) {
		int curType = 0, retIfCageFit = 0;

		curType = getTypeOfAvailableCage();
		while (curType > 0) {
			retIfCageFit = ifCageFitIn(curType);
			
			// the whole layout is covered by cages.
			if (retIfCageFit == 0) {
				if (getTypeOfAvailableCage() == 0) {
					// no available cage left. find one possible layout. 
					if (numOfSolutions < MAX_LAYOUTSOLUTIONS) {
						ArrayList<Integer> possibleLayout = new ArrayList<Integer>();
						if (copyResult(possibleLayout) == 0) {
							possibleLayout.add(gameSize);
							possibleLayouts.add(possibleLayout);
						}
					}
					numOfSolutions++;
					if (numOfSolutions > MAX_POSSIBLE_LAYOUTS) {
						return -3;		// too many results
					}
					
					// try to find other possible layouts
					curType = replaceLastCage();
				} else {
					// too many cages
					return -1;
				}
				
			// part of layout is not covered by cages
			} else if (retIfCageFit == 1) {
				curType = getTypeOfAvailableCage();
				if (curType == 0) {
					return -2; 	// not enough cages.
				}
				
			// the cage cannot be fit into the layout
			} else {
				// try next type of cage
				curType = getNextTypeOfCage(curType);
				if (curType == 0) {
					curType = replaceLastCage();
				}
			}
		}
		return numOfSolutions;
	}
	
	private void deleteValsByRowsAndColumns(Cell c) {		
		Cell tmpCell = null;
		
		// search the cells in the same column.
		for (int i = 1; i <= gameSize; i++) {
			tmpCell = rows.get(gameSize * (i - 1) + c.x - 1);
			// delete the values exist in the above cells within the same column.
			if (i < c.y) {
				Integer val = tmpCell.value;
				c.possibleValues.remove(val);
				
			// remove the values in the cage whose size is 1
			} else if (i > c.y) {
				if (tmpCell.cage.cageSize == 1) {
					Integer val = tmpCell.cage.targetNumber;
					c.possibleValues.remove(val);
				}
			}
		}		
		
		// search the cells in the same row
		for (int i = 1; i <= gameSize; i++) {
			tmpCell = rows.get(gameSize * (c.y - 1) + i - 1);
			// delete the values exist in the left cells within the same row
			if (i < c.x) {
				Integer val = tmpCell.value;
				c.possibleValues.remove(val);
			
			// 
			} else if (i > c.x) {
				if (tmpCell.cage.cageSize == 1) {
					Integer val = tmpCell.cage.targetNumber;
					c.possibleValues.remove(val);
				}
			}
		}
	}
	
	// set possible values for the last cell of the cage which has SUB or DIV operator
	private int setLastCellofSUBDIVCage(Cage pCage, Cell c) {
		ArrayList<Cell> arrCells = pCage.cells;
		int maxVal = pCage.targetNumber;
		int bigResult = pCage.targetNumber;		
		int smlResult = (pCage.operator == Cage.OP_SUB ? 0 : 1);
		boolean ifTgtSmaller = false;	// if targetnumber is smaller than one of the values of cells

		for (int i = 0; i < arrCells.size(); i++) {
			int cellVal = arrCells.get(i).value;

			if (cellVal == 0) {
				continue;
			}
			// get the bigger possible value of the cell
			if (pCage.operator == Cage.OP_SUB) {
				bigResult += cellVal;
			} else {
				bigResult *= cellVal;
			}

			// get the smaller one
			if (maxVal > cellVal) {
				if (pCage.operator == Cage.OP_SUB) {
					smlResult += cellVal;
				} else {
					smlResult *= cellVal;
				}
			} else {
				if (pCage.operator == Cage.OP_SUB) {
					smlResult += maxVal;
				} else {
					smlResult *= maxVal;
				}
				maxVal = cellVal;
				ifTgtSmaller = true;
			}
		}

		if (bigResult > 0 && bigResult <= gameSize) {
			c.possibleValues.add(bigResult);
		}

		if (ifTgtSmaller) {
			if (pCage.operator == Cage.OP_SUB) {
				smlResult = maxVal - smlResult;
			} else {
				int tmp = smlResult;
				
				tmp = maxVal / smlResult;		// should not be a float
				if (maxVal != tmp * smlResult) {
					smlResult = 0;
				} else {
					smlResult = tmp;
				}
			}
			if (smlResult > 0 && smlResult <= gameSize) {
				c.possibleValues.add(smlResult);
			}
		}
		
		return c.possibleValues.size();
	}

	/*
	 * return value: positive integer means the number of the possible values,
	 * negative integer means the reason why there is no possible value
	 */
	private int getPossibleValues(Cell c) {
		int numOfValues = c.possibleValues.size();
		
		if (numOfValues > 0) {
			return numOfValues;
		}
		
		// if the cell has been set a value
		if (c.value != 0) {
			return -1;		// go back to the left cell
		}
		
		// obviously no solutions
		Cage pCage = c.cage;
		if ((pCage.operator == Cage.OP_SUB && pCage.targetNumber >= gameSize)
			|| (pCage.operator == Cage.OP_DIV && pCage.targetNumber > gameSize)) {
			return -4;
		}
		
		// a cage with only one cell
		if (pCage.operator == Cage.OP_EQU) {
			c.possibleValues.add(c.cage.targetNumber);
			return 1;
		}
		
		// add all the possible values by the rule of the cage
		// NOTE: Each cell MUST have one possible value.
		// first, get the first possible value for cage with ADD & MUL operator
		ArrayList<Cell> arrCells = pCage.cells;
		int resultVal = pCage.targetNumber;
		int numOfCellsWithVal = 0;
		
		for (int i = 0; i < arrCells.size(); i++) {
			// just compared the cells of the cage prior to current one
			if (!(arrCells.get(i).x <= c.x && arrCells.get(i).y <= c.y)) {
				continue;
			}
			int cellVal = arrCells.get(i).value;
			
			if (cellVal == 0) {
				continue;
			}
			numOfCellsWithVal++;
			switch (pCage.operator) {
			case Cage.OP_ADD:
				resultVal -= cellVal;
				break;
			case Cage.OP_MUL:
				int tmp = resultVal;
				
				tmp /= cellVal;
				if (resultVal != tmp * cellVal) {		// should not be a float
					// go back to the last cell of the cage.
					return -3;
				}
				resultVal = tmp;
				break;
			}
		}
		
		// If it is the last one of the cage
		if (pCage.cageSize - 1 == numOfCellsWithVal) {
			if ((resultVal < 1 && pCage.operator == Cage.OP_ADD) || resultVal > gameSize) {
				// go back to the last cell of the cage.
				return -3;		
			}
			if (pCage.operator == Cage.OP_SUB || pCage.operator == Cage.OP_DIV) {
				// set possible values for the last cell 
				if (setLastCellofSUBDIVCage(pCage, c) == 0) {
					return -3;
				}
			} else {
				c.possibleValues.add(resultVal);
			}
			deleteValsByRowsAndColumns(c);
			return c.possibleValues.size();
		}
		
		// else, add all the other possible values
		switch (pCage.operator) {
		case Cage.OP_ADD:
			if (pCage.cageSize - numOfCellsWithVal > 1) {
				resultVal--;	// the smallest value of the last cell should be 1.
			}
			if (resultVal > gameSize) {
				resultVal = gameSize;
			}
			while (resultVal > 0 && resultVal <= gameSize) {
				c.possibleValues.add(resultVal--);
			}
			break;
		case Cage.OP_MUL:
			if (resultVal > gameSize) {
				resultVal = gameSize;
			}
			while (resultVal > 0 && resultVal <= gameSize) {
				int tmp = pCage.targetNumber / resultVal;
				
				if (pCage.targetNumber == tmp * resultVal) {
					// the targetNumber can be divided by the possible value in integer. 
					c.possibleValues.add(resultVal);
				}
				resultVal--;
			}
			break;
		case Cage.OP_SUB:
		case Cage.OP_DIV:
			resultVal = 1;
			while (resultVal <= gameSize) {
				c.possibleValues.add(resultVal++);
			}
			break;
		}
		deleteValsByRowsAndColumns(c);
		
		return c.possibleValues.size();
	}

	private Cell getLeftCell(Cell c) {
		if (c.x == 1 && c.y == 1) {
			return null;
		}
		return rows.get(gameSize * (c.y - 1) + c.x - 2);
	}
	
	private Cell getRightCell(Cell c) {
		if (c.x == gameSize && c.y == gameSize) {
			return null;
		}
		return rows.get(gameSize * (c.y - 1) + c.x);
	}
	
	private Cell getCellofLastRow(Cell c) {
		if (c.y == 1) {
			return null;
		}
		return rows.get(gameSize * (c.y - 2) + c.x - 1);
	}
	
	// search the cage from right to left, down to up
	private Cell getLastCellofCage(Cell c) {
		if (c.x == 1 && c.y == 1) {
			return null;
		}

		int i = gameSize * (c.y - 1) + c.x - 2;
		Cell leftCell = null;
		
		while (i >= 0) {
			leftCell = rows.get(i);
			if (c.cage == leftCell.cage) {
				return leftCell;
			}
			i--;
		}
		return null;	// do not find the cell.
	}
	
	/*
	 * Recursively set the cell value with all the possible values 
	 * from left to right, up to down.
	 */
	private int try2SetCellValue(Cell c) {
		if (c == null) {
			return -1;
		}
		
		int ret = getPossibleValues(c); 
		
		if (ret > 0) {
			// set a possible value to the cell
			c.value = c.possibleValues.get(0);
			c.possibleValues.remove(0);

			// if it is the last cell
			if (c.x == gameSize && c.y == gameSize) {
				// Succeed finding one solution
				numOfSolutions++;
				
				if ((gameSize > 5 && numOfSolutions > 1) 
						|| numOfSolutions > Layout.MAX_SOLUTIONS) {
					return numOfSolutions;
				}
				
				// try to test the next possible value of the same cell
				return try2SetCellValue(c);
			}
			
			// clear the possibleValues of the next cell in order to get the new possibleValues
			Cell nextCell = getRightCell(c);
			nextCell.possibleValues.clear();
			nextCell.value = 0;
			//logger.printSolution(this, c);
			return try2SetCellValue(nextCell);
		}
		
		// find no possible value
		if (ret == -4) {
			return -4;
		} else if (ret == -3) {
			return try2SetCellValue(getLastCellofCage(c));
		} else if (ret == -2) {
			return try2SetCellValue(getCellofLastRow(c));
		} else {
			if (c.x == 1 && c.y == 1) {
				return 0;		// Over. All the possible values have been tried.
			}
			return try2SetCellValue(getLeftCell(c));
		}		
	}
	
	private int getNumOfPossibleSolutions() {
		// clear up the data
		numOfSolutions = 0;
		for (int i = 0; i < cages.size(); i++) {
			for (int j = 0; j < cages.get(i).cells.size(); j++) {
				cages.get(i).cells.get(j).possibleValues.clear();
				cages.get(i).cells.get(j).valueBackup = cages.get(i).cells.get(j).value;
				cages.get(i).cells.get(j).value = 0;
			}
		}
		
		try {
			try2SetCellValue(rows.get(0));
		} catch (StackOverflowError e) {
			logger.err("getNumOfPossibleSolutions: StackOverflowError");
			return -5;
		}

		// restore the data
		for (int i = 0; i < cages.size(); i++) {
			for (int j = 0; j < cages.get(i).cells.size(); j++) {
				cages.get(i).cells.get(j).value = cages.get(i).cells.get(j).valueBackup;
			}
		}

		return numOfSolutions;
	}
	
	private int clearCages() {
		cages.clear();
		rows.clear();
		columns.clear();
		numOfSolutions = 0;
		return 0;
	}
	
	// convert number list to layout structure
	// a connection between the result of project 2 and the input of project 4.
	private int convertNumlist2LayoutStructure(ArrayList<Integer> lstNumbers) {
		clearCages();
		
		int gSize = lstNumbers.get(lstNumbers.size() - 1);		// game size
		for (int i = 0; i < gSize; i++) {
			for (int j = 0; j < gSize; j++) {
				Cage c = null;
				Cell e = new Cell();
				int index = i * gSize + j;
				
				e.x = j + 1;
				e.y = i + 1;
				e.data = lstNumbers.get(index);
				
				if (j > 0 && lstNumbers.get(index) == lstNumbers.get(index - 1)) {
					c = rows.get(index - 1).cage;
				} else if (i > 0 && lstNumbers.get(index) == lstNumbers.get(index - gSize)) {
					c = rows.get(index - gSize).cage;
				} else {
					c = new Cage();
					cages.add(c);
				}
				c.cells.add(e);
				c.cageSize++;
				e.cage = c;
				
				rows.add(e);
			}
		}
		gameSize = gSize;
		
		return 0;
	}
	
	// set a value to the cell(row,column)
	private int addOneValue(int x, int y) {
		int val = rows.get(x * gameSize + y).value + 1;
		
		for (int i = val; i <= gameSize; i++) {
			boolean bFind = false;

			// find if the value has been used in the row
			for (int j = 0; j < y; j++) {
				if (rows.get(x * gameSize + j).value == i) {
					bFind = true;
					break;
				}
			}
			// find if the value has been used in the column
			if (!bFind) {
				for (int j = 0; j < x; j++) {
					if (rows.get(j * gameSize + y).value == i) {
						bFind = true;
						break;
					}
				}
			}
			if (!bFind) {
				rows.get(x * gameSize + y).value = i;
				return i;
			}
		}
		return 0;
	}
	
	// calculate target number and generate text format formulas
	private int generateTxtFormulas() {
		txtFileFormulas.clear();
		
		for (int i = 0; i < cages.size(); i++) {
			Cage c = cages.get(i);
			StringBuffer sb = new StringBuffer();
			int val = 0;
			
			// get the target number
			switch (c.operator) {
			case Cage.OP_ADD:
				for (int j = 0; j < c.cells.size(); j++) {
					val += c.cells.get(j).value;
				}
				sb.append(val + " + ");
				break;
			case Cage.OP_MUL:
				val = 1;
				for (int j = 0; j < c.cells.size(); j++) {
					val *= c.cells.get(j).value;
				}
				sb.append(val + " * ");
				break;
			case Cage.OP_SUB:
				for (int j = 0; j < c.cells.size(); j++) {
					val = val > c.cells.get(j).value ? val : c.cells.get(j).value;
				}
				val *= 2;
				for (int j = 0; j < c.cells.size(); j++) {
					val -= c.cells.get(j).value;
				}
				if (val < 0) {
					return -1;
				}
				sb.append(val + " - ");
				break;
			case Cage.OP_DIV:
				for (int j = 0; j < c.cells.size(); j++) {
					val = val > c.cells.get(j).value ? val : c.cells.get(j).value;
				}
				val *= val;
				for (int j = 0; j < c.cells.size(); j++) {
					if (val % c.cells.get(j).value != 0) {
						return -1;
					}
					val /= c.cells.get(j).value;
				}
				sb.append(val + " / ");
				break;
			case Cage.OP_EQU:
				sb.append(c.cells.get(0).value + " = ");
				break;

			default:
				return -1;
			}
			
			// get text format formula
			sb.append(c.cells.size() + " ");
			for (int j = 0; j < c.cells.size(); j++) {
				char row = (char) ('A' + c.cells.get(j).y - 1);
				char col = (char) ('0' + c.cells.get(j).x);

				sb.append("" + row + col + " ");
			}
			txtFileFormulas.add(sb.toString());
			c.targetNumber = val;
		}		
		return 0;
	}
	
	private int cntLayoutWithFormulas = 0;

	// recursively add all possible formulas to the layout
	private int addPossibleFormulas() {
		for (int i = 0; i < cages.size(); i++) {
			if (i < 0) {
				break;
			}
			Cage c = cages.get(i);
			
			if (c.cageSize == 1) {
				c.operator = Cage.OP_EQU;
			} else {
				c.operator++;
				if (c.operator == Cage.OP_EQU) {
					// go back to previous cage
					c.operator = 0;
					i = i - 2;
				}
			}
			if (i == cages.size() - 1) {
				// find one layout with formula and cell values
				// check if it has only one solution
				if (generateTxtFormulas() == 0) {
					int ret = getNumOfPossibleSolutions();
					
					if (ret < 0) {
						logger.output("Failed to getNumOfPossibleSolutions()");
						return -1;
					}
					
					if (ret == 1) {
						logger.printOutGame(this);
						
						cntLayoutWithFormulas++;
						if ((gameSize == 3 && cntLayoutWithFormulas >= MAX_POSSIBLE_LAYOUTS) ||
								(gameSize == 4 && cntLayoutWithFormulas >= MAX_POSSIBLE_LAYOUTS / 10)) {
							logger.output("Too many results (more than " + cntLayoutWithFormulas + ") for this layout. The other results will not be printed out.\n");
							i = -99;
							break;
						}
					} else {
//						logger.output("Number of possible solutions for above layout: " + ret);
//						logger.output("\n");
					}
				} else {
					// go back to previous cage
					// TODO: go back to the wrong formula cage
					c.operator = 0;
					i--;
				}
				i--;
			}
		}
		return 0;
	}
	
	// generate all possible layouts with formulas, all layouts should only have ONE solution
	public int generateLayoutWithFormulas(ArrayList<Integer> lstNumbers) {
		// construct layout structure
		convertNumlist2LayoutStructure(lstNumbers);
		
		// fill in the layout with possible numbers
		int column = 0;
		for (int i = 0; i < gameSize; i++) {
			if (i < 0) {
				break;	// tried all possible numbers for all cells.
			}
			for (int j = column; j < gameSize; j++) {
				if (j < 0) {
					i = i - 2;	// go back to the previous row
					column = gameSize - 1;
					break;
				}
				if (j + 1 == gameSize && i + 1 == gameSize) {
					if (addOneValue(i, j) == 0) {
						logger.err("Failed to addOneValue (" + i + "," + j + ")");
					} else {
						// now the cells are full of values, try to add possible formulas.
						//logger.printOutGame(this);
						cntLayoutWithFormulas = 0;
						if (addPossibleFormulas() != 0) {
							return -1;
						}
					}
					
					// go back to the previous column
					rows.get(i * gameSize + j).value = 0;
					j = j - 2;
					continue;
				}

				if (addOneValue(i, j) == 0) {				
					if (i == 0 & j == 0) {
						// exit
						i = -99;
						break;
					} else if (j == 0) {
						// go back to the previous row
						rows.get(i * gameSize + j).value = 0;
						i = i - 2;
						column = gameSize - 1;
						break;
					} else {
						// go back to the previous column
						rows.get(i * gameSize + j).value = 0;
						j = j - 2;
					}
				} else if (j == gameSize - 1) {
					column = 0;
				}
			}
		}
		return 0;
	}

}
